1. Field
Apparatuses and methods consistent with the exemplary embodiments of the inventive concept relate to encoding and decoding Low Density Parity Check (LDPC) codes, and more particularly, to encoding and decoding LDPC codes which perform LDPC encoding and decoding based on a parity-check matrix.
2. Description of the Related Art
In a communication/broadcasting system, link performance may considerably deteriorate due to various types of noises, a fading phenomenon, and inter-symbol interference (ISI) of a channel. Therefore, to implement high-speed digital communication/broadcasting systems requiring high data throughput and reliability like next-generation mobile communications, digital broadcasting, and portable Internet, it has been required to develop technologies to overcome the noises, the fading, and the inter-symbol interference. As part of studies to overcome the noises, etc., a study on an error-correcting code which is a method for increasing reliability of communications by efficiently recovering distorted information has been actively conducted recently.
LDPC codes which were first introduced by Gallager in the 1960s remain forgotten for a very long time due to complexity which could hardly be implemented at the technology level at that time. However, as performance of turbo codes proposed by Berrou, Glavieux, and Thitimajshima in 1993 approaches Shannon's channel capacity, many studies on channel encoding based on iterative decoding and a graph thereof by performing many different interpretations on performance and characteristics of the turbo codes have been conducted. As a result, as the LDPC codes in the late 1990s are restudied, when the LDPC codes are decoded by applying sum-product algorithm based iterative decoding to the LDPC codes on a tanner graph corresponding to the LDPC codes, it was found that the performance of the LDPC codes approaches the Shannon's channel capacity.
The LDPC codes may be generally defined by a parity-check matrix and represented using a bipartite graph commonly referred to as the tanner graph.
Hereinafter, a systematic LDPC codeword will be described with reference to FIG. 1. The LDPC codes are LDPC encoded by receiving an information word 102 formed of Kldpc bits or symbols to generate a codeword 100 formed of Nldpc bits or symbols. Hereinafter, for convenience of explanation, it is assumed that the codeword 100 formed of Nldpc bits is generated by receiving the information word 102 including Kldpc bits. That is, when the information word I=[i0, i1, i2, . . . , iKldpc−1] 102 which is formed of Kldpc input bits is LDPC encoded, the codeword c=[c0, c1, c2, c3, . . . , cKldpc−1] 100 is generated. That is, the codeword is a bit string formed of a plurality of bits and the bits of the codeword represent each bit forming the codeword. Further, the information word is a bit string formed of a plurality of bits and the bits of the information word represent each bit forming the information word. In this case, in the case of a systematic code, the codeword is formed of c=[c0, c1, c2, . . . , cNldpc−1]=[i0, i1, i2, . . . , iKldpc−1, p0, p1, p2, . . . , pNldpc−Kldpc−1]. Here, P=[p0, p1, p2, . . . , pNldpc−Kldpc−1] is a parity 104 and the number Nparity of parity bits is as follows. Nparity=Nldpc−Kldpc.
The LDPC codes are a kind of linear block codes and include a process of determining a codeword satisfying conditions of following mathematical expression 1.H·cT=[h0,h1,h2, . . . ,hNldpc−1]·cT=Σi=0Nldpc−1ci·hi=0  (1)where c=[c0, c1, c2, . . . , cNldpc−1].
In mathematical expression 1 above, H represents the parity-check matrix, C represents the codeword, ci represents an i-th bit of the codeword, and Nldpc represents a codeword length. Here, hi represents an i-th column of the parity-check matrix H.
The parity-check matrix H is formed of the same Nldpc columns as the number of bits of the LDPC codeword. The mathematical expression 1 represents that since a sum of a product of the i-th column hi of the parity-check matrix and the i-th bit ci of the codeword becomes “0”, the i-th column hi has a relationship with the i-th bit ci of the codeword.
Meanwhile, the performance of the LDPC codes may be determined according to the parity-check matrix. Therefore, there is a need to design the parity-check matrix for the LDPC codes having improved performance.